#include <stdexcept>

#include "big_int.h"

big_int::big_int() : shift_(0), negative_(false)
{
   digits_.push_back(0);
}

big_int::big_int(long long digit) : shift_(0), negative_(digit < 0)
{
   digits_.push_back(std::abs(digit));
}

big_int::big_int(const big_int& bigint) : shift_(bigint.shift_), negative_(bigint.negative_)
{
   digits_ = bigint.digits_;
}

big_int::big_int(const std::string& str) : shift_(0), negative_(false)
{   
   int begin = 0;
   
   negative_ = (str[0] == '-');
   if (str[0] == '-' || str[0] == '+')
   {
      begin = 1;
   }

   size_t counter = 0;
   digit_t tmp = 0;

   digits_.clear();

   int len = str.length();
   for (int i = len - 1; i >= begin; i--)
   {
      if (counter == big_int::DIGIT_LENGTH)
      {
         digits_.push_back(tmp);
         tmp = 0;
         counter = 0;
      }

      int d = (str[i] - '0');
      for (size_t i = 0; i < counter; i++)
      {
         d *= 10;
      }
      tmp += d;
      counter++;
   }

   digits_.push_back(tmp);
   
   if (digits_.size() == 0)
   {
      digits_.push_back(0);
   }
   
   cut_zeroes();
}

big_int& big_int::operator=(const big_int& bigint)
{
   if (this == &bigint)
   {
      return *this;
   }
   
	negative_ = bigint.negative_;
	shift_ = bigint.shift_;
	digits_ = bigint.digits_;

	return *this;
}

void big_int::swap(big_int& bigint)
{
   std::swap(shift_, bigint.shift_);
   std::swap(negative_, bigint.negative_);
   digits_.swap(bigint.digits_);
}

big_int big_int::abs() const
{
   return (negative_ ? -*this : *this);
}

int big_int::compare_to(const big_int& bigint) const
{
   if (negative_ && !bigint.negative_)
   {
      return -1;
   }
   if (!negative_ && bigint.negative_)
   {
      return 1;
   }
   if (negative_ && bigint.negative_)
   {
      return -(abs().compare_to(bigint.abs()));
   }
   
   if (digits_.size() + shift_ != bigint.digits_.size() + bigint.shift_)
   {
      if (digits_.size() + shift_ < bigint.digits_.size() + bigint.shift_)
      {
         return -1;
      }
      else
      {
         return 1;
      }
   }
   int len = digits_.size();
   for (int i = len - 1; i >= 0; i--)
   {
      int j = i - bigint.shift_ + shift_;
      digit_t d = (0 <= j && j < static_cast<int>(bigint.digits_.size())) ? bigint.digits_[j] : 0;
      if (digits_[i] < d) {
         return -1;
      }
      if (digits_[i] > d) {
         return 1;
      }
   }
   return 0;
}

bool big_int::operator<(const big_int& bigint) const
{
   return compare_to(bigint) < 0;
}

bool big_int::operator>(const big_int& bigint) const
{
   return compare_to(bigint) > 0;
}

bool big_int::operator<=(const big_int& bigint) const
{
   return compare_to(bigint) <= 0;
}

bool big_int::operator>=(const big_int& bigint) const
{
   return compare_to(bigint) >= 0;
}

bool big_int::operator==(const big_int& bigint) const
{
   return compare_to(bigint) == 0;
}

bool big_int::operator!=(const big_int& bigint) const
{
   return compare_to(bigint) != 0;
}

big_int& big_int::operator+=(const big_int& bigint)
{
   if (bigint == big_int(0))
   {
      return *this;
   }
   
   if (!negative_ && bigint.negative_)
   {
      return *this -= bigint.abs();
   }
   if (negative_ && !bigint.negative_)
   {
      big_int tmp = (*this).abs();
      *this = bigint;
      return *this -= tmp;
   }
   if (negative_ && bigint.negative_)
   {
      *this = (*this).abs();
      *this += bigint.abs();
      *this = -(*this);
      return *this;
   }
   
   if (digits_.size() + shift_ < bigint.digits_.size() + bigint.shift_)
   {
      digits_.resize(bigint.digits_.size() + bigint.shift_ - shift_, 0);
   }

   if (shift_ > bigint.shift_)
   {
      digits_.insert(digits_.begin(), shift_ - bigint.shift_, 0);
      shift_ = bigint.shift_;
   }
   
   int len = bigint.digits_.size();
   for (int i = 0; i < len; i++)
   {
      unsigned int k = i - shift_ + bigint.shift_;
      digits_[k] += bigint.digits_[i];
   }

   normalize();
   
   cut_zeroes();
   
   return *this;
}

big_int& big_int::operator-=(const big_int& bigint)
{
   if (bigint == big_int(0))
   {
      return *this;
   }
   
   if (!negative_ && bigint.negative_)
   {
      return *this += bigint.abs();
   }
   if (negative_ && !bigint.negative_)
   {
      *this = -((*this).abs() + bigint);
      return *this;
   }
   if (negative_ && bigint.negative_)
   {
      *this = bigint.abs() - (*this).abs();
      return *this;
   }
   
   if (bigint > *this)
   {
      *this = -(bigint - *this);
      return *this;
   }
   
   if (shift_ > bigint.shift_)
   {
      digits_.insert(digits_.begin(), shift_ - bigint.shift_, 0);
      shift_ = bigint.shift_;
   }
   
   int len = bigint.digits_.size();
   for (int i = 0; i < len; i++)
   {
      unsigned int k = i - shift_ + bigint.shift_;
      digits_[k] -= bigint.digits_[i];
   }

   normalize();

   cut_zeroes();

   return *this;
}

big_int& big_int::operator*=(long long digit)
{
   if (digit == 0)
   {
      *this = big_int(0);
      return *this;
   }
   
   int len = digits_.size();
   for (int i = 0; i < len; i++)
   {
      digits_[i] *= digit;
   }

   normalize();

   return *this;
}

big_int& big_int::operator*=(const big_int& bigint)
{
   if (bigint == big_int(0))
   {
      *this = big_int(0);
      return *this;
   }
   
   big_int tmp;
   
   int len = bigint.digits_.size();
   for (int i = len - 1; i >= 0; i--)
   {
      tmp *= BASE;
      tmp += (*this) * bigint.digits_[i];
   }
   
   tmp.negative_ = (tmp != big_int(0)) && (negative_ != bigint.negative_);
   
   *this = tmp;
   return *this;
}

big_int& big_int::operator/=(const big_int& bigint)
{
   if (bigint.abs() == big_int(0))
   {
      throw std::runtime_error("Division by zero!");
   }
   *this = divide_with_remainder(bigint).first;
   
   return *this;
}

big_int& big_int::operator%=(const big_int& bigint)
{
   if (bigint.abs() == big_int(0))
   {
      throw std::runtime_error("Division by zero!");
   }
   *this = divide_with_remainder(bigint).second;
   
   return *this;
}

big_int big_int::operator+(const big_int& bigint) const
{
   big_int tmp = *this;
   tmp += bigint;
   
   return tmp;
}

big_int big_int::operator-(const big_int& bigint) const
{
   big_int tmp = *this;
   tmp -= bigint;
   
   return tmp;
}

big_int big_int::operator*(const big_int& bigint) const
{
   big_int tmp = *this;
   tmp *= bigint;
   
   return tmp;
}

big_int big_int::operator/(const big_int& bigint) const
{
   big_int tmp = *this;
   tmp /= bigint;
   
   return tmp;
}

big_int big_int::operator%(const big_int& bigint) const
{
   big_int tmp = *this;
   tmp %= bigint;
   
   return tmp;
}

big_int big_int::operator*(long long digit) const
{
   big_int tmp = *this;
   tmp *= digit;

   return tmp;
}

big_int big_int::operator-() const
{   
   big_int tmp = *this;
   tmp.negative_ = (tmp != big_int(0)) && !tmp.negative_;
   
   return tmp;
}

std::pair<big_int, big_int> big_int::divide_with_remainder(const big_int& bigint) const
{   
   big_int a = (*this).abs();
   big_int b = bigint.abs();
   big_int result;
   
   int shift = a.digits_.size() - b.digits_.size();
   b <<= shift;

   while (a >= bigint.abs())
   {
      digit_t k = a.find_short_divider(b);
      result <<= 1;
      result += big_int(k);
      a -= b * k;
      b >>= 1;
      shift--;
   }

   if (shift + 1 > 0)
   {
      result <<= shift + 1;
   }
   result.cut_zeroes();

   result.negative_ = (result != big_int(0)) && (negative_ != bigint.negative_);
   a.negative_ = (a != big_int(0)) && negative_;
   
   return std::make_pair(result, a);
}

big_int& big_int::operator<<=(int shift)
{
   shift_ += shift;

   return *this;
}

big_int& big_int::operator>>=(int shift)
{
   shift_ -= shift;

   return *this;
}

big_int big_int::operator<<(int shift) const
{
   big_int tmp = *this;
   tmp <<= shift;

   return tmp;
}

big_int big_int::operator>>(int shift) const
{
   big_int tmp = *this;
   tmp >>= shift;

   return tmp;
}

std::istream& operator>>(std::istream &is, big_int &bigint)
{
   while (std::isspace(is.peek()))
   {
      is.get();
   }
   
   std::ostringstream ss;
   
   if (is.peek() == '-' || is.peek() == '+')
   {
      char sign;
      is.get(sign);
      ss << sign;
   }
   
   if (!isdigit(is.peek())) {
      is.setstate(std::ios_base::badbit);
      return is;
   }

   while (isdigit(is.peek()))
   {
      char tmp;
      is.get(tmp);
      ss << tmp;
   }
   
   bigint = big_int(ss.str());

   return is;
}

std::ostream& operator<<(std::ostream &os, const big_int &bigint)
{
   if (bigint.negative_)
   {
      os << "-";
   }
   
   int size = bigint.digits_.size();
   for (int i = size - 1; i >= 0; i--)
   {
      std::ostringstream out;
      out << bigint.digits_[i];
      std::string str = out.str();

      if (i != size - 1)
      {
         int count = big_int::DIGIT_LENGTH - str.length();
         for (int i = 0; i < count; i++)
         {
            os << "0";
         }
      }

      os << str;
   }

   std::string zero(bigint.DIGIT_LENGTH, '0');
   for (int i = 0; i < bigint.shift_; i++)
   {
      os << zero;
   }

   return os;
}

void big_int::normalize()
{
   digit_t carry;
   
   int size = digits_.size();
   for (int i = 0; i < size - 1; i++)
   {
      if (digits_[i] >= BASE)
      {
         carry = digits_[i] / BASE;
         digits_[i] -= carry * BASE;
         digits_[i + 1] += carry;
      }
      if (digits_[i] < 0)
      {
         carry = std::abs((digits_[i] - BASE + 1) / BASE);
         digits_[i] += carry * BASE;
         digits_[i + 1] -= carry;
      }
   }
   
   carry = 0;
   while (true)
   {
      size_t last = digits_.size() - 1;
      
      if (digits_[last] < 0)
      {
         carry = -std::abs((digits_[last] - BASE + 1) / BASE);
         digits_[last] -= carry * BASE;
      }
      if (digits_[last] >= BASE)
      {
         carry = digits_[last] / BASE;
         digits_[last] -= carry * BASE;
      }

      if (carry == 0)
      {
         break;
      }
      else if (carry == -1)
      {
         *this = -((big_int(1) << digits_.size()) - *this);
         break;
      }
      else
      {
         digits_.push_back(carry);
         carry = 0;
      }
   }
}

long long big_int::find_short_divider(const big_int& bigint) const
{
   digit_t l = 0;
   digit_t r = BASE;
   digit_t m = (l + r) / 2;
   while (l + 1 != r)
   {
      if (*this < bigint * m)
      {
         r = m;
      }
      else
      {
         l = m;
      }
      m = (l + r) / 2;
   }

   return m;
}

void big_int::cut_zeroes()
{   
   while (digits_.size() > 1 && digits_[digits_.size() - 1] == 0)
   {
      digits_.pop_back();
   }
   
   if (digits_.size() == 1 && digits_[0] == 0)
   {
      shift_ = 0;
   }
}

big_int abs(const big_int& bigint)
{
   return bigint.abs();
}